package hashbuck;

import java.util.Arrays;

public class HashBuck {
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {m
            this.key = key;
            this.val = val;
        }
    }

    public Node[] arr;
    public int usedSize;
    //负载因子
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBuck(Node[] arr, int usedSize) {
        arr = new Node[10];
    }
    public void put(int key, int val) {
        //根据key和哈希函数来确定在数组中的下标
        int index = key % (arr.length);
        Node cur = arr[index];
        //查看之前是否存在key值,存在的话,更新val,不存在,进行头插法
        while (cur!=null) {
            if(cur.key==key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //不存在key值进行头插法
        Node newNode = new Node(key,val);
        newNode.next = arr[index];
        arr[index] = newNode;
        usedSize++;
        if(doLoadFactor()>=DEFAULT_LOAD_FACTOR) {
            //扩容
            //重新哈希
            //因为长度变了
            //原来位置冲突的元素可能放在新的数组的其他位置
            resize();
        }
    }

    private void resize() {
        Node[] newArray = new Node[arr.length*2];
        //遍历数组每个下标的链表,重新放到新数组
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            //遍历链表,重新哈希
            while (cur!=null) {
                //后面的步骤cur.next会被修改,所以在传向
                //链表的下一个结点时会出错,所以要提前记录下来
                Node tmpNode = cur.next;
                //确定在新数组中的下标
                int newIndex = cur.key%(newArray.length);
                //重新在新的数组中插入
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = tmpNode;
            }
        }
        arr = newArray;
    }


    private float doLoadFactor() {
        return usedSize*1.0f / arr.length;
    }

    public int get(int key) {
        //获取下标
        int index = key%arr.length;
        Node cur = arr[index];
        while (cur!=null) {
            //找到返回val值
            if(cur.key==key) {
                return cur.val;
            }
            //遍历链表
            cur = cur.next;
        }
        return -1;
    }
}
